package 中等.二分查找;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（
 * 两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 * 整数 a 比整数 b 更接近 x 需要满足：
 * |a - x| < |b - x| 或者
 * |a - x| == |b - x| 且 a < b
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-k-closest-elements
 */
public class 找到K个最接近的元素_658 {

    public static void main(String[] args) {

        找到K个最接近的元素_658 obj = new 找到K个最接近的元素_658();
        System.out.println(obj.findClosestElements(new int[]{-2, -1, 1, 2, 3, 4, 5}, 7, 3));

    }

    /**
     * 二分查找+双指针
     * 先通过二分查找，找到数组中最接近 x 的索引，剩下的 k-1 个，
     * 通过双指针在求出索引的左右两边取较接近的那个
     *
     * @param arr
     * @param k
     * @param x
     * @return
     */
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();
        int idx = findMinIdx(arr, x);
        k--;
        int left = idx - 1, right = idx + 1;
        while (k > 0) {
            if (right > arr.length - 1 || left >= 0 && Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) {
                left--;
            } else {
                right++;
            }
            k--;
        }
        // 最接近 x 的值，一定在 arr 中是连续的
        for (int i = left + 1; i <= right - 1; i++) {
            list.add(arr[i]);
        }
        return list;
    }

    private int findMinIdx(int[] arr, int x) {
        int left = 0, right = arr.length - 1, target = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (Math.abs(arr[mid] - x) < Math.abs(arr[target] - x) ||
                    Math.abs(arr[mid] - x) == Math.abs(arr[target] - x) && mid < target) {
                target = mid;
            }
            if (arr[mid] >= x) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return target;
    }

}
